package sort

import (
	"reflect"
	"sort"
	"strings"
	"unsafe"
)

// 每次从未排序的区域找到最小的放到已排序的末尾，初始已排序区域是没有的，未排序是整个数组，因此第一次需要遍历全部找到最小值
// 选择排序也是不稳定的，举例 5,4,5,3,2 第一次遍历，第一个5和2交换位置，第一个5跑到了数组最后，此时第一个5和第二个5的相对位置已经发生了改变
func SelectionSort(arr []int) {
	if len(arr) <= 2 {
		return
	}
	for i := 0; i < len(arr)-1; i++ {
		minIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		Swap(arr, i, minIndex)
	}
}

func InsertSort(arr []int) {
	if len(arr) <= 1 {
		return
	}

	for i := 0; i < len(arr); i++ {
		value := arr[i]
		// 从当前元素之前的区间开始对比，每出现一次前面的元素大于当前元素，大于的元素都要往后移动一格，直到找到小于等于该元素的位置，此时遍历结束
		// 并且遍历结束后，j指向的位置下一格是空位，因为大于的元素已经提前后移，所以最后将value插入j+1的位置即可
		j := i - 1
		for ; j >= 0; j-- {
			if arr[j] <= value {
				break
			}
			arr[j+1] = arr[j]
		}
		arr[j+1] = value
	}
}

func BubbleSort(arr []int) {
	if len(arr) <= 2 {
		return
	}
	for i := len(arr); i > 0; i-- {
		// 每次只交换了一个数到最后，因此需要上面的for循环做多次操作
		// 如果本次没有任何数需要交换证明已经有序
		flag := true
		for j := 0; j < i; j++ {
			if arr[j] > arr[j+1] {
				Swap(arr, j, j+1)
				flag = false
			}
		}
		if flag {
			break
		}
	}
}

func MergeSort(arr []int) {
	var deep func([]int)
	deep = func(s []int) {
		if len(s) == 1 {
			return
		}
		left, right := s[:len(s)/2], s[len(s)/2:]
		deep(left)
		deep(right)
		tmp := merge(left, right)
		if len(tmp) > 0 {
			copy(s, tmp)
		}
	}
	deep(arr)
}

/*
迭代思路是先1个1个合并，然后2个2个合并...以此类推
*/
func MergeSort1(arr []int) {
	if len(arr) == 1 {
		return
	}
	step := 1
	// 步长从1开始，先是1个1个合并，然后再是2个2个合并，当步长大于len(arr)/2时，为最后一次合并，因此跳出循环条件为 step < len(arr)
	for step < len(arr) {
		// 下标每次移动步长 1,2,4.....
		for i := 0; i < len(arr); i += step << 1 {

			//获取左数组的末尾
			mid := i + step
			// 获取右数组的末尾
			end := i + step<<1

			//如果左数组的末尾已经大于等于长度，证明只剩下一个有序数组，因此跳出循环
			if mid >= len(arr) {
				break
			}
			left := arr[i:mid]
			if end > len(arr) {
				end = len(arr)
			}

			right := arr[mid:end]
			// 如果不两个数组已经有序，则不需要合并，有序时tmp返回nil
			tmp := merge(left, right)
			if len(tmp) > 0 {
				copy(arr[i:end], tmp)
			}
		}
		step = step << 1
	}
}

//完成交换后，基准数左边的元素都 <= 基准数，这就要求最后一步交换前 nums[left] >= nums[i] 必须成立。
//假设我们先“从左往右查找”，那么如果找不到比基准数更大的元素，则会在 i == j 时跳出循环，此时可能 nums[j] == nums[i] > nums[left]。
//也就是说，此时最后一步交换操作会把一个比基准数更大的元素交换至数组最左端，导致哨兵划分失败。
//举个例子，给定数组 [0, 0, 0, 0, 1] ，如果先“从左向右查找”，哨兵划分后数组为 [1, 0, 0, 0, 0] ，这个结果是不正确的。

func QuickSort(arr []int, left, right int) {
	i := smallerPartition(arr, left, right)
	// 基准值位置不参与排序
	// 为何递归结束条件是 left >= right 而不是left == right
	// 还是以 0 0 0 1举例，此时i和j相遇的位置在第0个下标，i -1 = -1
	if i-1 > left {
		QuickSort(arr, left, i-1)
	}

	if i+1 < right {
		QuickSort(arr, i+1, right)
	}
}

func merge(left, right []int) []int {
	if left[len(left)-1] <= right[0] {
		return nil
	}

	tmp := make([]int, len(left)+len(right))
	index := 0
	i, j := 0, 0
	for i < len(left) || j < len(right) {
		if i < len(left) && j < len(right) {
			if left[i] <= right[j] {
				tmp[index] = left[i]
				i++
			} else {
				tmp[index] = right[j]
				j++
			}
		} else if i < len(left) {
			tmp[index] = left[i]
			i++
		} else if j < len(right) {
			tmp[index] = right[j]
			j++
		}
		index++
	}
	return tmp
}

func findKthLargest(arr []int, k int) int {
	index := biggerPartition(arr, 0, len(arr)-1)
	if index+1 == k {
		return arr[index]
	}
	if index+1 > k {
		return findKthLargest(arr[:index], k)
	}
	return findKthLargest(arr[index+1:], k-index-1)
}

func biggerPartition(arr []int, left, right int) int {
	pivot := arr[left]
	i, j := left, right
	for i < j {
		for i < j && arr[j] <= pivot {
			j--
		}

		for i < j && arr[i] >= pivot {
			i++
		}

		arr[i], arr[j] = arr[j], arr[i]
	}
	// 将基准值与i,j交会处替换
	arr[left], arr[i] = arr[i], arr[left]
	return i
}

func smallerPartition(arr []int, left, right int) int {
	pivot := arr[left]
	i, j := left, right
	for i < j {
		// 如果我们选取了left下标对应的元素做基准值，那么必须从右往左遍历

		// 一直循环直到找到右边小于基准值的元素，跳出循环
		for i < j && arr[j] >= pivot {
			j--
		}

		// 一直循环直到找到左边大于基准值的元素，跳出循环
		for i < j && arr[i] <= pivot {
			i++
		}

		arr[i], arr[j] = arr[j], arr[i]
	}
	// 将基准值与i,j交会处替换
	arr[left], arr[i] = arr[i], arr[left]
	return i
}

func Swap(arr []int, i, j int) {
	//arr[i] = arr[i] ^ arr[j]
	//arr[j] = arr[i] ^ arr[j]
	//arr[i] = arr[i] ^ arr[j]
	arr[i], arr[j] = arr[j], arr[i]
}

func simplifyPath(path string) string {
	pathStr := "/"
	split := strings.Split(path, pathStr)
	score := 0
	zeroIndex := -1
	length := len(split)
	for i := 1; i < length; i++ {
		val := split[i]
		if val == "." || val == "" {
			//do nothing
		} else if split[i] == ".." {
			score += 1
		} else {
			score -= 1
		}

		if score == 0 {
			zeroIndex = i + 1
		}
	}

	sb := strings.Builder{}
	sb.WriteString(pathStr)
	startIndex := 1
	if zeroIndex != -1 {
		startIndex = zeroIndex
	}
	for ; startIndex < length-1; startIndex++ {
		val := split[startIndex]
		if val == "" {
			continue
		}
		sb.WriteString(val)
		sb.WriteString(pathStr)
	}
	if val := split[startIndex]; val != "" {
		sb.WriteString(val)
	} else {
		result := sb.String()
		return result[:len(result)-1]
	}
	return sb.String()
}

func quickSort(nums []int, left, right int) {
	makeMid(nums, left, right)
	q := nums[left]

	i, j := left, right
	for i < j {
		for i < j && nums[j] >= q {
			j--
		}

		for i < j && nums[i] <= q {
			i++
		}

		nums[i], nums[j] = nums[j], nums[i]
	}
	// 从尾部还是遍历，i,j交汇时，此处的值一定小于等于基准值
	nums[left], nums[i] = nums[i], nums[left]
	if left < i-1 {
		quickSort(nums, left, i-1)
	}
	if i+1 < right {
		quickSort(nums, i+1, right)
	}
}

func makeMid(nums []int, left, right int) {
	x, y, z := nums[left], nums[(left+right)/2], nums[right]

	avg := (x + y + z) / 3
	if x > avg {
		if y > z {
			nums[left], nums[(left+right)/2] = nums[(left+right)/2], nums[left]
		}
		nums[left], nums[right] = nums[right], nums[left]
	} else if y > avg && x < z {
		nums[left], nums[right] = nums[right], nums[left]
	}

	if z > avg && x < y {
		nums[left], nums[(left+right)/2] = nums[(left+right)/2], nums[left]
	}
}

func BucketSort(nums []float64) {
	bucketNum := len(nums) / 2
	buckets := make([][]float64, 0, bucketNum)
	length := len(nums) / bucketNum
	for i := 0; i < len(buckets); i++ {
		buckets[i] = make([]float64, 0, length)
	}

	for _, n := range nums {
		// 个人认为：理想的下标计算 元素除以(最大值除以桶个数) 即 n/(max-min/k)，例如最大数为1000，最小为0，假设我们分为100个桶，元素5/((1000-0) /10) = 0
		// 而第一个桶的理想范围也为0-10，因此元素5在下标为0的桶
		// 此处的max为1,min为0，因此下标计算应为 n / ((1-0)/bucketNum),即n * bucketNum
		bucket := buckets[int(n*float64(bucketNum))]
		bucket = append(bucket, n)
	}
	for i := 0; i < len(buckets); i++ {
		val := buckets[i]
		sort.Float64s(val)
	}
	nums = nums[:0]
	for i := 0; i < len(buckets); i++ {
		nums = append(nums, buckets[i]...)
	}
}

func CountSort(nums []int) {
	max := nums[0]
	// 找到最大值即可
	for _, n := range nums {
		if n > max {
			max = n
		}
	}

	// 统计每个值出现的次数，值为数组下标
	temp := make([]int, max+1)
	for _, n := range nums {
		temp[n] += 1
	}

	// temp是为了保证稳定性，如果不需要考虑稳定性，则得到temp数组后直接填充即可
	count := make([]int, len(temp))
	count[0] = temp[0]
	result := count[0]
	// 将temp内的元素前面逐渐相加，得到count数组
	for i := 1; i < len(temp); i++ {
		result += temp[i]
		count[i] = result
	}

	r := make([]int, len(nums))
	for i := len(nums) - 1; i >= 0; i-- {
		val := nums[i]
		index := count[val] - 1
		r[index] = val
		count[val] -= 1
	}
	copy(nums, r)
}

func HeapSort(nums []int) {
	//buildHeapDownTop(nums)
	buildHeapTopDown(nums)
	n := len(nums) - 1
	for n > 0 {
		nums[0], nums[n] = nums[n], nums[0]
		n--
		heapfiy(nums, n, 0)
	}
}

func buildHeapTopDown(nums []int) {
	p := func(i int) int {
		if i < 0 {
			return i
		}
		return i >> 1
	}

	for i := range nums {
		current := i
		parent := p(current - 1)

		for parent >= 0 && nums[current] >= nums[parent] {
			nums[current], nums[parent] = nums[parent], nums[current]
			current = parent
			parent = p(current - 1)
		}
	}
}

func buildHeapDownTop(nums []int) {
	n := len(nums) - 1
	// 从最后一个非叶子节点开始，依次往前建堆
	for i := (n - 1) / 2; i >= 0; i-- {
		// 保证每一个根节点及其子堆都是合法堆
		heapfiy(nums, n, i)
	}
}

func heapfiy(nums []int, n, index int) {
	for {
		suiteIndex := index
		left := index<<1 + 1
		right := left + 1

		if left <= n && nums[suiteIndex] < nums[left] {
			suiteIndex = left
		}

		if right <= n && nums[suiteIndex] < nums[right] {
			suiteIndex = right
		}

		if suiteIndex == index {
			break
		}
		nums[index], nums[suiteIndex] = nums[suiteIndex], nums[index]
		index = suiteIndex
	}
}

// RadixSortStrings 排序字符串
func RadixSortStrings(phoneNumbers []string) {
	length := len(phoneNumbers[0])
	for index := length - 1; index >= 0; index-- {
		sort.SliceStable(phoneNumbers, func(i, j int) bool {
			return getNthByte(phoneNumbers[i], index) < getNthByte(phoneNumbers[j], index)
		})
	}
}

func RadixSortNumbers(nums []int) {
	length := 0
	r := nums[0]
	for {
		r = r / 10
		length++
		if r == 0 {
			break
		}
	}

	for index := length; index >= 1; index-- {
		sort.SliceStable(nums, func(i, j int) bool {
			return getNthNumber(nums[i], index, length) < getNthNumber(nums[j], index, length)
		})
	}
}

func getNthNumber(number, n, length int) int {
	times := length - n
	for times > 0 {
		number = number / 10
		times--
	}
	return number % 10
}

func getNthByte(s string, n int) byte {
	bytes := *(*reflect.StringHeader)(unsafe.Pointer(&s))
	b := *(*[]byte)(unsafe.Pointer(&bytes))
	return b[n]
}
